We propose convolutional deep averaging networks (CDANs) for classifying and learning feature representations of datasets containing instances with unordered features, where each feature is considered a tuple composed of one or more values. CDANs accept variable-size input and are invariant to permutations of the input's order. In addition, as a side-effect of the training process, CDANs learn discriminative, nonlinear embeddings of individual input elements into a space of chosen dimensionality. Contrary to their name, which is inspired by the work of Iyyer et al. [11], CDANs could perhaps be more accurately termed convolutional deep pooling networks as we also consider the effects of functions other than averaging such as taking element-wise maximums or sums. A. Contributions We propose CDANs for classifying unordered feature sets. We show that a CDAN with nonlinear embeddings is competitive with and perhaps even superior to recurrent neural networks (RNNs) and known permutation-invariant architectures for classifying instances containing variablesize sets of unordered features. We also find that the type of pooling plays a significant role in determining the efficacy of the network with sum-pooling clearly outperforming maxand average-pooling.

In this paper, we study the problem of designing objective functions for machine learning problems defined on finite \emph{sets}. In contrast to traditional objective functions defined for machine learning problems operating on finite dimensional vectors, the new objective functions we propose are operating on finite sets and are invariant to permutations. Such problems are widespread, ranging from estimation of population statistics \citep{poczos13aistats}, via anomaly detection in piezometer data of embankment dams \citep{Jung15Exploration}, to cosmology \citep{Ntampaka16Dynamical,Ravanbakhsh16ICML1}. Our main theorem characterizes the permutation invariant objective functions and provides a family of functions to which any permutation invariant objective function must belong. This family of functions has a special structure which enables us to design a deep network architecture that can operate on sets and which can be deployed on a variety of scenarios including both unsupervised and supervised learning tasks. We demonstrate the applicability of our method on population statistic estimation, point cloud classification, set expansion, and image tagging.

We introduce a simple permutation equivariant layer for deep learning with set structure.This type of layer, obtained by parameter-sharing, has a simple implementation and linear-time complexity in the size of each set. We use deep permutation-invariant networks to perform point-could classification and MNIST-digit summation, where in both cases the output is invariant to permutations of the input. In a semi-supervised setting, where the goal is make predictions for each instance within a set, we demonstrate the usefulness of this type of layer in set-outlier detection as well as semi-supervised learning with clustering side-information.